// this function should return the minist number of coins needed to make the amount
// the denominations are [1, 2, 5, 10, 20, 30, 50, 100]
pub fn dp_rec_mc(amount: u32) -> u32 {
    let denominations = vec![1, 2, 5, 10, 20, 30, 50, 100];
    let mut cache = vec![0; amount as usize + 1];
    for i in 1..amount + 1 {
        let mut min = std::u32::MAX;
        for &denom in denominations.iter() {
            if i >= denom {
                let temp = cache[(i - denom) as usize] + 1;
                if temp < min {
                    min = temp;
                }
            }
        }
        cache[i as usize] = min;
    }
    cache[amount as usize]
}
